﻿//////////////////////////////////////////////////////////////////////////
// @brief 二叉堆
// @author youdang0809
// @date 2012-10-19
// @details <算法说明>
//////////////////////////////////////////////////////////////////////////

#ifndef HEAP_H
#define HEAP_H

#if !defined(NULL)
#   define NULL 0
#endif

#if !defined(MAX_HEAP)
#   define MAX_HEAP 0
#endif
#if !defined(MIN_HEAP)
#   define MIN_HEAP 1
#endif

struct heap_node
{
    int key;    ///< 键
    void *data; ///< 数据指针
};

struct heap
{
    int size;                ///< 节点个数
    int capacity;            ///< 容量
    int type;                ///< 堆类型（MAX_HEAP, MIN_HEAP）
    struct heap_node *nodes; ///< 节点数组指针
};

//////////////////////////////////////////////////////////////////////////
// 堆初始化函数
// @param hp 指向一个堆的指针
// @param type 大顶堆（MAX_HEAP），小顶堆（MIN_HEAP）
// @return 初始化成功返回0，错误返回-1
//////////////////////////////////////////////////////////////////////////
extern int heap_init(struct heap *hp, int type);

//////////////////////////////////////////////////////////////////////////
// 堆插入函数
// @param hp 指向堆的指针
// @param key 键值
// @param data 数据指针
// @return 插入成功返回0，错误返回-1
//////////////////////////////////////////////////////////////////////////
extern int heap_insert(struct heap *hp, int key, void *data);

//////////////////////////////////////////////////////////////////////////
// 堆删除函数（删除堆根节点）
// @param hp 指向堆的指针
// @return 删除成功返回根节点指针，错误返回NULL
//////////////////////////////////////////////////////////////////////////
extern struct heap_node *heap_delete(struct heap *hp);

//////////////////////////////////////////////////////////////////////////
// 堆查找函数
// @param hp 指向堆的指针
// @param key 待查找节点的键值
// @return 查找到节点则返回该节点指针，未找到返回NULL
//////////////////////////////////////////////////////////////////////////
extern struct heap_node *heap_find(struct heap *hp, int key);

//////////////////////////////////////////////////////////////////////////
// 对已建立好的堆排序函数
// @param hp 指向堆的指针
//////////////////////////////////////////////////////////////////////////
extern void heap_sort(struct heap *hp);

#endif // HEAP_H